package com.ibm.rules.tree;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.google.common.base.Preconditions;
import com.google.common.collect.BoundType;
import com.google.common.collect.Range;
import com.google.common.collect.TreeMultimap;
import com.ibm.cps.message.ParsedDataMessage;
import com.ibm.datamodel.timeseries.parser.ProtostuffMessageParser;
import com.ibm.interfaces.ITimeSeriesSchema;
import com.ibm.rules.RangeEndPoint;
import com.ibm.rules.RangeEndPoint.PointType;
import com.ibm.rules.Rule;
import com.ibm.rules.RuleEntry;
import com.ibm.rules.RulePartition;
import com.ibm.rules.RuleRangeMap;
import com.ibm.util.ComparablePair;
import com.ibm.util.DataTypes;
import com.ibm.util.exception.CPSException;

import scala.Char;

public abstract class RuleTreeNode {
	protected static final int PARTITION_PENALTY = 30;
	protected static final int SPLIT_THRESHOLD = 3;
	static private Logger logger = LoggerFactory
			.getLogger(ProtostuffMessageParser.class);

	private static int log2nlz(int bits) {
		if (bits == 0)
			return 1;
		return 31 - Integer.numberOfLeadingZeros(bits);
	}

	static protected <T extends Comparable<T>> RuleTreeNode feedWithType(
			ITimeSeriesSchema tags, int tagId, Rule[] rules, int maxRangeSize,
			RuleRangeMap valueMap, T instance) throws CPSException {

		RulePartition<T> partition = getPartition(tagId, rules, maxRangeSize,
				valueMap, instance);
		logger.debug(String
				.format("rule number: %d; pnum: %d; map cost: %d; biggest range: %d; tree cost: %d",
						rules.length,
						partition.partitionNumber(),
						log2nlz(partition.partitionNumber()),
						partition.getBiggestRangeSize(),
						log2nlz(partition.partitionNumber())
								+ partition.getBiggestRangeSize()
								+ PARTITION_PENALTY));
		if (rules.length > log2nlz(partition.partitionNumber())
				+ partition.getBiggestRangeSize() + PARTITION_PENALTY) {
			PartitionRuleTreeNode parent = new PartitionRuleTreeNode(partition);
			Iterator<Entry<Range<T>, RuleTreeNode>> iter = partition
					.getRanges();
			Entry<Range<T>, RuleTreeNode> now = iter.next();
			Entry<Range<T>, RuleTreeNode> next = null;
			List<PartitionRuleTreeNode> toMerge = new ArrayList<PartitionRuleTreeNode>();
			while (iter.hasNext()) {
				next = iter.next();
				Range<T> range = now.getKey();
				RuleTreeNode nowNode = now.getValue();
				Preconditions
						.checkArgument(nowNode instanceof LeafRuleTreeNode);

				LeafRuleTreeNode nowLeaf = (LeafRuleTreeNode) nowNode;

				/* prune unnecessary conditions */
				nowLeaf.removeRedundantCondition(tagId, range);

				RuleTreeNode node = feed(tags, nowLeaf.getRules());
				if (node instanceof PartitionRuleTreeNode) {
					if (((PartitionRuleTreeNode) node).getPartition()
							.getTagId() == partition.getTagId()) {
						toMerge.add((PartitionRuleTreeNode) node);
					} else {
						now.setValue(node);
					}
				}

				now = next;
			}

			for (PartitionRuleTreeNode node : toMerge) {
				parent.mergeNode(node);
			}

			return parent;
		} else {
			/*
			 * the rules are not replicated at this level, so no need to deep
			 * copy
			 */
			return new LeafRuleTreeNode(rules);
		}
	}

	private static Rule[] cloneToArray(Rule[] rules, Set<Integer> idSet) {
		Rule[] results = new Rule[idSet.size()];
		Iterator<Integer> iter = idSet.iterator();
		int i = 0;
		while (iter.hasNext()) {
			int id = iter.next();
			results[i++] = new Rule(rules[id]);
		}
		return results;
	}

	@SuppressWarnings("rawtypes")
	static private <T extends Comparable<T>> RulePartition<T> getPartition(
			int tagId, Rule[] rules, int upperRangeSize, RuleRangeMap valueMap,
			T instance) {
		RulePartition<T> partition = RulePartition.<T> create(tagId);
		Iterator<Entry<ComparablePair<Comparable, Byte>, Collection<RangeEndPoint>>> iter = valueMap
				.entrySet().iterator();
		int ref = 0;
		Set<Integer> accRuleIdSet = new TreeSet<Integer>();
		Set<Integer> curRuleIdSet = new TreeSet<Integer>();
		ComparablePair<Comparable, Byte> lastEndValue = null;
		boolean first = true;
		while (iter.hasNext()) {
			Entry<ComparablePair<Comparable, Byte>, Collection<RangeEndPoint>> entry = iter
					.next();
			ComparablePair<Comparable, Byte> endValue = entry.getKey();
			Collection<RangeEndPoint> endPoints = entry.getValue();

			if (first) {
				first = false;
				partition.firstEndPoint(endValue);
			}

			Iterator<RangeEndPoint> epIter = endPoints.iterator();
			while (epIter.hasNext()) {
				RangeEndPoint now = epIter.next();
				if (now.getPointType() == PointType.Start) {
					ref++;
				}
			}

			if (ref > upperRangeSize) {
				/* current point cannot be included into the range */
				Preconditions.checkNotNull(lastEndValue,
						"first endpoint exceeds the upperbound");

				/* deep copy the rules as we might modify it later */
				LeafRuleTreeNode node = new LeafRuleTreeNode(cloneToArray(
						rules, accRuleIdSet));
				partition.nextEndPoint(lastEndValue, node, endValue);
				accRuleIdSet = new TreeSet<Integer>(curRuleIdSet);
				ref = accRuleIdSet.size();
			}

			lastEndValue = endValue;
			epIter = endPoints.iterator();
			while (epIter.hasNext()) {
				RangeEndPoint now = epIter.next();
				int ruleId = now.getRuleId();
				if (now.getPointType() == PointType.Start) {
					accRuleIdSet.add(ruleId);
					curRuleIdSet.add(ruleId);
				} else { /* END */
					curRuleIdSet.remove(ruleId);
				}
			}
		}

		/* deep copy the rules as we might modify it later */
		LeafRuleTreeNode node = new LeafRuleTreeNode(cloneToArray(rules,
				accRuleIdSet));
		partition.nextEndPoint(lastEndValue, node, null);
		return partition;
	}

	/**
	 * Construct the rule tree given the rule set
	 * 
	 * @param tags
	 * @param rules
	 * @return the root node of the rule tree
	 * @throws CPSException 
	 */
	static public RuleTreeNode feed(ITimeSeriesSchema tags, Rule[] rules) throws CPSException {
		Map<Integer, RuleRangeMap> valueMaps = new HashMap<Integer, RuleRangeMap>();

		ComparablePair<Integer, Integer> idAndRangeSize = getTagIdWithMinimalMaxRange(
				tags, rules, valueMaps);
		int tagId = idAndRangeSize.getFirst();
		int maxRangeSize = idAndRangeSize.getSecond();
		if (DataTypes.isFloatOrDouble(tags.getDataType(tagId))) {
			return feedWithType(tags, tagId, rules, maxRangeSize,
					valueMaps.get(tagId), Double.valueOf(0));
		} else {
			return feedWithType(tags, tagId, rules, maxRangeSize,
					valueMaps.get(tagId), Long.valueOf(0));
		}

	}
	
	// need to support field array.
	@SuppressWarnings({ "rawtypes" })
	static private ComparablePair<Integer, Integer> getTagIdWithMinimalMaxRange(
			ITimeSeriesSchema tags, Rule[] rules, Map<Integer, RuleRangeMap> outMaps) {
		HashMap<Integer, TreeMultimap<ComparablePair<Comparable, Byte>, RangeEndPoint>> valueMaps = new HashMap<Integer, TreeMultimap<ComparablePair<Comparable, Byte>, RangeEndPoint>>();
		
		
		/*step 1: build a mapping from array-tag id to origin tag id */
		Set<Integer> tagIdSet = new HashSet<>();
		for (int i = 0; i < rules.length; i++) {
			RuleEntry[] entries = rules[i].getEntries().clone();
			for (int j = 0; j < entries.length; j++) {
				tagIdSet.add(entries[j].getTagId());
			}
			
		}
		
		
		Iterator<Integer> idIter = tagIdSet.iterator();
		while (idIter.hasNext()) {
			Integer tagId = (Integer) idIter.next();
			valueMaps.put(tagId, TreeMultimap
					.<ComparablePair<Comparable, Byte>, RangeEndPoint> create());
		}

		// all tag ranges for a user rule
		for (int i = 0; i < rules.length; i++) {
			RuleEntry[] entries = rules[i].getEntries().clone();
			Arrays.sort(entries);
			int j = 0;
			while (j < entries.length && entries[j] == null)
				j++;
			
			Iterator<Integer> it = tagIdSet.iterator();
			while (it.hasNext()) {
				Integer tagId = (Integer) it.next();
				TreeMultimap<ComparablePair<Comparable, Byte>, RangeEndPoint> nowValueMap = valueMaps.get(tagId);
				if (j < entries.length && tagId == entries[j].getTagId()) {
					/* the condition is for this tag */
					Range range = entries[j].getRange();
					byte lowerValueType = (byte) (range.lowerBoundType() == BoundType.OPEN ? 1
							: 0);
					nowValueMap.put(
							new ComparablePair<Comparable, Byte>(range
									.lowerEndpoint(), lowerValueType),
							new RangeEndPoint(PointType.Start, i));
					byte upperValueType = (byte) (range.upperBoundType() == BoundType.OPEN ? 0
							: 1);
					nowValueMap.put(
							new ComparablePair<Comparable, Byte>(range
									.upperEndpoint(), upperValueType),
							new RangeEndPoint(PointType.End, i));
					while (j < entries.length && entries[j] == null)
						j++;
				} else {
					if (DataTypes.isFloatOrDouble(tags.getDataType(tagId))||DataTypes.isDoubleArray(tags.getDataType(tagId))) {
						nowValueMap.put(new ComparablePair<Comparable, Byte>(
								DataTypes.getMinValue(Double.valueOf(0)),
								(byte) 0),
								new RangeEndPoint(PointType.Start, i));
						nowValueMap.put(new ComparablePair<Comparable, Byte>(
								DataTypes.getMaxValue(Double.valueOf(0)),
								(byte) 1), new RangeEndPoint(PointType.End, i));
					} else if (DataTypes.isIntOrLong(tags.getDataType(tagId))||DataTypes.isLongArray(tags.getDataType(tagId))){
						nowValueMap.put(new ComparablePair<Comparable, Byte>(
								DataTypes.getMinValue(Long.valueOf(0)),
								(byte) 0),
								new RangeEndPoint(PointType.Start, i));
						nowValueMap.put(new ComparablePair<Comparable, Byte>(
								DataTypes.getMaxValue(Long.valueOf(0)),
								(byte) 1), new RangeEndPoint(PointType.End, i));
					} else if (DataTypes.isString(tags.getDataType(tagId))||DataTypes.isStringArray(tags.getDataType(tagId))){
						nowValueMap.put(new ComparablePair<Comparable, Byte>(
								DataTypes.getMinValue(String.valueOf(0)),
								(byte) 0),
								new RangeEndPoint(PointType.Start, i));
						nowValueMap.put(new ComparablePair<Comparable, Byte>(
								DataTypes.getMaxValue(String.valueOf(0)),
								(byte) 1), new RangeEndPoint(PointType.End, i));
					}
				}
			}
		}
		int minTagId = -1, minRefCount = Integer.MAX_VALUE, maxRefCount = 0;

		Iterator<Integer> it = tagIdSet.iterator();
		while (it.hasNext()) {
			Integer tagId = (Integer) it.next();
			int ref = 0;
			maxRefCount = 0;
			TreeMultimap<ComparablePair<Comparable, Byte>, RangeEndPoint> nowValueMap = valueMaps.get(tagId);
			outMaps.put(tagId,new RuleRangeMap(nowValueMap.asMap()));

			Iterator<Entry<ComparablePair<Comparable, Byte>, Collection<RangeEndPoint>>> iter = outMaps.get(tagId)
					.entrySet().iterator();
			while (iter.hasNext()) {
				Entry<ComparablePair<Comparable, Byte>, Collection<RangeEndPoint>> entry = iter
						.next();
				Iterator<RangeEndPoint> endPointIter = entry.getValue()
						.iterator();
				while (endPointIter.hasNext()) {
					PointType pointType = endPointIter.next().getPointType();
					if (pointType == PointType.Start) {
						ref++;
					} else {
						ref--;
					}
					if (maxRefCount < ref) {
						maxRefCount = ref;
					}
				}
				if (maxRefCount >= minRefCount)
					break;
			}

			if (iter.hasNext())
				continue;

			if (minRefCount > maxRefCount) {
				minRefCount = maxRefCount;
				minTagId = tagId;
			}
		}
		return new ComparablePair<Integer, Integer>(minTagId, minRefCount);
	}

	/**
	 * 
	 * @param rule
	 * @return 
	 * 		false indicate a rebuild is needed for the rule tree; 
	 * 		true indicate the tree performance is still acceptable.
	 */
	public abstract boolean addIncrementalRule(Rule rule) throws CPSException;

	@SuppressWarnings("rawtypes")
	public abstract Collection<BigInteger> executeAllRules(Comparable[] fact)
			throws CPSException;
	
	public abstract Collection<BigInteger> executeAllRules(ParsedDataMessage message)
			throws CPSException;

	public abstract void deleteRuleByName(String ruleName) throws CPSException;
}
